package william.matrix;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/4/27
 * @description <a href="https://leetcode.cn/problems/spiral-matrix/description/">...</a>
 */
public class Leetcode54_螺旋矩阵 {
    /**
     * 采用按层遍历的方式
     * 记录矩阵左、右、上、下4个边界,分别为left、right、top、bottom
     * Step1: 从左到右遍历,路径为: (top,left) -> (top,right)
     * Step2: 从上到下遍历,路径为: (top+1,right) -> (bottom,right)
     * Step3: 如果right>left,且bottom>top,则继续从右到左遍历,路径为: (bottom,right-1) -> (bottom,left)
     * Step4: 从下到上遍历,路径为: (bottom-1,left) -> (top+1,left)
     * Step5: 继续处理下一层: left++ right-- top++ bottom--
     * <p>
     * 时间复杂度O(M*N) 即矩阵长度*矩阵高度
     * 空间复杂度O(1)
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        //边界条件校验
        if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
            return Collections.emptyList();
        }

        //记录矩阵左、右、上、下4个边界,分别为left、right、top、bottom
        int M = matrix.length;
        int N = matrix[0].length;
        int left = 0;
        int right = N - 1;
        int top = 0;
        int bottom = M - 1;

        //按层遍历矩阵
        List<Integer> result = new ArrayList<>();
        while (left <= right && top <= bottom) {
            //Step1: 从左到右遍历,路径为: (top,left) -> (top,right)
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }

            //Step2: 从上到下遍历,路径为: (top+1,right) -> (bottom,right)
            for (int i = top + 1; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }

            //Step3: 如果right>left,且bottom>top,则继续从右到左遍历,路径为: (bottom,right-1) -> (bottom,left)
            if (left < right && top < bottom) {
                for (int i = right - 1; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }

                //Step4: 从下到上遍历,路径为: (bottom-1,left) -> (top+1,left)
                for (int i = bottom - 1; i >= top + 1; i--) {
                    result.add(matrix[i][left]);
                }
            }


            //Step5: 继续处理下一层: left++ right-- top++ bottom--
            left++;
            right--;
            top++;
            bottom--;
        }


        //返回结果
        return result;

    }
}
